DATABASE THEORY (236356)
Winter Semester 2010/11
Last given Winter Semester 2001/02
Course details
Course Home Page:
http://www.cs.technion.ac.il/~janos/COURSES/236356-10
Projects
for final grade:
Received Projects
Lecturer: Prof. J.A. Makowsky
Tirgul: NN
Language: Hebrew or English (if required) , Reading assignments in English
Time: Monday: 14:30-16:30 Lecture, 16:30-17:30 Tirgul
Place: Lecture and Tirgul in Taub 4 (CS Building)
FIRST MEETING: MONDAY, 18.10. 2010, 14:30
Previously Given: Winter 94/95, Spring 1997, Winter 2000/01, Winter 2001/02
Prerequisites and Requirements:
Logic 1 (2342920) necessary and
Database Systems (236363).
The course will mainly follow [1,2,6] below.
Take home exam or project.
Abstracts of each lecture will
be available together with further references.
Course outline:
This course gives the Logical Foundations of the
theory of relational data bases and the ER-formalism.
Its main topics
are the semantics of data base specifications and of
query languages. Complexity issues will also be discussed.
The first part of the course is Dependency Theory and
its relationship to data modelling.
The second part of the course concerns the theory of Query Languages
and the foundation of Logic Programming (Datalog).
Both parts are based on the relational model of data bases.
In a third part of the course alternative data models of
theoretical significance will be discussed:
-
Constraint Databases.
-
XML Data Models.
These topics will be discussed
depending on time and audience.
We shall reach a level where topics for research can be
formulated both for M.Sc. and Ph.D. candidates.
Textbooks
- * S. Abiteboul, R. Hull and V. Vianu,
Foundations of Databases , Addison-Wesley 1995
- * H. Mannila and K.J. Raiha, The Design of Relational
Databases , Addison-Wesley 1992
- * G. Kuper, Leonid Libkin and J. Paredaens (Eds.),
Constraint Databases, Springer 2000.
- P.C. Kannelakis, Elements of Relational Database Theory,
in: Handbook of Theoretical Computer Science, volume 2, chapter 17.
J. van Leeuwen, ed., Elsevier Science Publishers, 1990.
- J. Paredaens, P. De Bra, M. Gyssens and D. van Gucht,
The Structure of the relational database model,
EATCS Monographs on Theoretical Computer Science, vol. 17,
Springer Verlag 1989
Preprints of recent
research relevant for the course (under construction! List from 2002).
Further Literature
-
Review of the books Foundations of
Databases,
The Design of Relational databases
and Kannelakis' handbook article
by J.A. Makowsky, from the Journal of
Symbolic Logic.
- H.D. Ebbinghaus and J. Flum, Finite Model Theory,
Springer 1996
J. Ullmann, Principles of data base systems,
Computer science press, 1980ff.
- D. Maier, The theory of relational databases,
Computer science press, 1983.
- A. Chandra and D. Harel, Computable queries,
JCSS 21.2 (1980).
- J.A.Makowsky, Review of [1, Ullman], [2, Maier] and [3, Chandra
and Harel], in
Journal of Symbolic Logic 51.4 (1987).
- M. Vardi, Fundamentals of dependency theory,
in: Trends in theoretical computer science (E.Boerger ed.),
Computer science press, 1988.
-
J.A. Makowsky and E. Ravve ,
Translation Schemes and the Fundamental problem of Database
Design (invited lecture)
(Published in: Conceptual Modeling - ER'96, B. Thalheim
(ed.), LNCS vol. 1157 (1996) pp. 5-26)